package hashdemo;

/**
 * @Author 比特就业课
 * @Date 2022-11-15
 */
public class HashBucket {
    public static void main(String[] args) {
        HashBucket hashBucket = new HashBucket();
        hashBucket.put(1,10);
        hashBucket.put(9,10);
        hashBucket.put(3,10);
        hashBucket.put(4,10);
        hashBucket.put(5,10);
        hashBucket.put(6,10);
        hashBucket.put(7,10);
        hashBucket.put(8,10);
    }
    // 定义一个节点对象
    private static class Node {
        int key;
        int value;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义哈希桶
    private Node[] bucket;
    // 当前有效元素的个数
    private int size;
    // 定义负载因子
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBucket () {
        bucket = new Node[8];
    }

    /**
     * 写入操作
     * @param key
     * @param value
     * @return
     */
    public int put (int key, int value) {
        //计算哈希值找位置
        int hash=key% bucket.length;
        //在具体位置找节点
        Node cur=bucket[hash];
        //这个位置存在元素
        while(cur!=null){
            if(cur.key==key){
                int oldValue= cur.value;
                cur.value=value;
                return oldValue;

            }
            //不断向下遍历
            cur=cur.next;
        }
        //如果当前链表为空或者找不到value相同的结点，那么建立新节点即可
        Node node = new Node(key, value);
        //头插法插入链表
        node.next=bucket[hash];
        bucket[hash]=node;
        size++;
        //判断是否需要扩容
        if((size+0.0)/ bucket.length>=DEFAULT_LOAD_FACTOR){
            //进行扩容操作
            resize();
        }

        return value;
    }

    public int get (int key) {
        //寻找对应的下标
        int index=key% bucket.length;
        //定义辅助结点进行遍历
        Node cur=bucket[index];
        while(cur!=null){
            if(cur.key==key){
                return cur.value;
            }
            //向后移动结点
            cur=cur.next;
        }

        return -1;
    }

//扩容方法的实现
    public void resize(){
        Node[]arrs=new Node[bucket.length*2];
        //对数组进行遍历
        for(int i=0;i<bucket.length;++i){
            //定义临时结点进行遍历
            Node cur=bucket[i];
            while(cur!=null){
                //先将后一个节点进行保存
                Node next=cur.next;
                //找在新队列中对应的位置
                int index= cur.key% arrs.length;
                //将节点进行转移
                cur.next=arrs[index];
                arrs[index]=cur;

                cur=next;//向后遍历
            }
        }
        //最后将新老队列进行交换
        bucket=arrs;
    }



}
